\section{Autentizačné protokoly s heslami}

Predstavme si veľmi klasickú situáciu. Použivateľ $A$ sa chce pripojiť
na server $S$ , čo obnáša samozrejme potvrdenie vlastnej identity.
V dnešnom svete je asi najbežnejšie overenie identity cez kombináciu
uživateľského mena a hesla $P$. A následne počas tohoto overenia
by sme chceli aj vygenerovať kľúč pre šifrovanie dát počas nasledovnej
komunikácie (session key $K$).

Pokiaľ ale navrhneme protokol zle narážame na jeden problém. Priestor
hesiel, ktoré sa bežne používajú je dosť malý. Na ten sa dá dosť úspešne
útočiť, či už úplným preberaním alebo slovníkovým útokom (keďže veľa použivateľov
má heslá, ktoré sú zmysluplné slová). Demonštrujme si to na jednoduchom
príklade protokolu:
\begin{enumerate}
\item $A \to S\colon A$ - uživateľ povie svoje meno
\item $S \to A\colon E_p(K)$ - server pomocou hesla zašifruje session key
\item $A \to S\colon E_k(msg)$ - uživateľ zašifruje vopred dohodnutú správu, aby ukázal, že dostal správny kľúč
\end{enumerate}

Tento protokol má niekoľko problémov. Okrem toho, že je náchýlný
na útok opakovaním, tak po zachytení druhej a tretej správy vieme úspešne útočiť
preberaním všetkých hesiel, keďže pre každé heslo, vieme povedať, či je správne alebo nie.

\subsection{EKE protokol}

Trochu lepším prístupom je EKE (Encrypted key exchange) protokol vymyslený 
v roku 1992. Má viacero variantov. Jednou z nich je napríklad DHEKE:

\begin{enumerate}
\item $A\to S\colon A, E_p(g^x)$
\item $S\to A\colon E_p(g^y), E_K(N_S)$, kde $K = g^{xy}$
\item $A\to S\colon E_K(N_A, N_S)$
\item $S\to A\colon E_K(N_A)$
\end{enumerate}

Čiže v podstate prebehne DH algoritmus, ktorý je ale šifrovaný heslom a navyše
si uživateľ a server vymenia príležitostné slová.
Iné varianty EKE môžu fungovať bez výmeny príležitostných slov prípadne využijú asymetrické
šifrovanie ($A\to S\colon A, E_p(pk_a)$; $S\to A\colon E_p(E_{pk_a}(K))$).

Tento protokol sa zdá byť bezpečný, keďže útočník po odposluchu sekvencie nie je schopný
robiť slovníkový útok. A šifrovanie heslom navyše zabraňuje man-in-the-middle útoku.

Ale je tu niekoľko problémov. Jednak $pk_a$, resp. $g^x$ musia byť úplne náhodne.
Napríklad verejný kľúč RSA $(n,e)$ je úplne nevhodný, keďže v ňom platí, že $e$ je nepárne
a nesúdeliteľný s $n$. Z tejto znalosti vie útočník po vyskúšaní všetkých hesiel približne polovicu vylúčiť.
Pokiaľ odpočuje viac konverzácií, tak sa časom dostane k správnemu heslu. Tomuto sa hovorí partitioning attack.
Podobná situácia je pri $g^x \pmod m$, kde niektoré hodnoty nemôžeme vôbec dostať a toto vie útočník
rozoznať.

A navyše je tu ďalší problém. Server musí udržiavať heslá v otvorenej podobe, čo má dosť
veľké bezpečnostné problémy. Môžeme miesto hesla si ukladať a používať na šifrovanie napríklad hash hesla (a tou aj šifrovať), ale
to stále nebráni útočníkovi napodobniť použivateľa, keď získa túto hash.

Tento problém sa snaží riešiť Augmented EKE protokol (A-EKE).
Zoberme si funkciu, ktorá
nám z hesla vygeneruje kľúče pre asymetrické podpisovanie: 
$\langle sk_A, pk_A \rangle = f(P)$. 
Server si uloží iba hodnotu $pk_A$.
Protokol bude podobný ako EKE, teda budeme šifrovať \emph{symetricky}
pomocou kľúča odvodeného z hesla, v našom prípade to bude $pk_A$.
Nakoniec pomocou súkromného kľúča (ktorý vie zostrojiť iba vlastník hesla)
podpíšeme komunikáciu a tým zaručíme, že komunikujeme s pravým človekom.

\begin{enumerate}
    \item $A\to S\colon A, E_{pk_A}(g^x)$.
        Pozor, v celej schéme šifrujeme iba \emph{symetricky}!
    \item $S\to A\colon E_{pk_A}(g^y), E_K(N_S)$
    \item $A\to S\colon E_K(N_S, N_A)$
    \item $S\to A\colon E_K(N_A)$
    \item $A\to S\colon E_K(Sig_{sk_A}(K))$ --
        tento krok je tu navyše oproti EKE, slúži nato,
        aby útočník pokiaľ získa $pk_A$ sa nevedel vložiť do
        komunikácie.
\end{enumerate}

\subsection{SRP (Secure remote password) protokol}

Ďalším protokolom použiteľným na autentifikáciu heslom je SRP protokol.
Pracuje v grupe $Z_n^{*}$, kde $n$ je prvočíslo. Nech $g$ je generátor
tejto grupy.
Pre každého uživateľa $A$ je potrebné vygenerovať náhodnú soľ $s$.
Privátnym kľúčom účastníka v ďalšom výpočte bude hash hesla, čiže
hodnota $x = H(s,P)$ a jeho verejný kľúč označíme ako $v = g^x$.
Server $S$ si následne
pre každého uživateľa uloží záznam $\langle A, s, v \rangle$.
Samotné prihlasovanie prebieha nasledovne:
\begin{enumerate}
\item $A\to S\colon A$
\item $S\to A\colon s$
\item $A\to S\colon \alpha = g^a$ pričom $a \inr Z_n^{*}$
\item $S\to A\colon \beta = g^b + v,\ u$ pričom $b,u \inr Z_n^{*}$
\item Server vypočíta kľúč $K = H((\alpha v^u)^b)$
\item Uživateľ vypočíta kľúč $K = H((\beta - g^x)^{a+ux})$
\item $A\to S\colon M_1 = H(A,S,K)$
\item $S\to A\colon H(A,M_1,K)$
\end{enumerate}

Ukážme si najprv, že aj server aj užívateľ vypočítajú tú istú hodnutu $K$.
Ak si odmyslíme hašovanie na konci, dostávame
\begin{align*}
(\beta - g^x)^{a+ux} = (g^b + v - g^x)^{a+ux} &= g^{ba+bux}\\
(\alpha v^u)^b = (g^{a+xu})^b &= g^{ba+bux}
\end{align*}
Zaoberajme sa teraz rôznymi vlastnosťami tohoto protokolu.

Prvou bude to, že útočník, ktorý odpočuje protokol,
nie je schopný vypočítať kľúč $K$.
Útočník má k dispozícií hodnoty $\alpha, \beta, u, g, n$.
Dajme mu navyše k dispozícii aj hodnotu $x$.
Ak útočník dokáže zistiť z týchto hodnôt hodnotu $K$,
vieme ho využiť na riešenie DH problému nasledovne:
Majme na vstupe hodnoty $g, g^a, g^b$. Zvolíme si $u,x$ tak, 
aby $n-1 | ux$, napríklad $u = 2, x = \frac{n-1}{2}$.
Útočníkovi dáme na vstup $\alpha = g^a, \beta = g^b + g^x$ a obvyklý zbytok.
On určí $K = H(g^{ba+bux})$. 
Vzhľadom na to, že uvažujeme hash ako náhodné orákulum,
tak je jasné, že niekedy musel útočník vedieť hodnotu $g^{ba+bux}$,
teda spýtať sa hašovacieho orákula na $H(g^{ba+bux})$.
Toto orákulum môžeme prevádzkovať útočníkovi sami a
tým pádom budeme vedieť hodnotu
$g^{ba+bux} = g^{ba+b(n-1)m} = g^{ba}$,
čím sme vyriešili úspešne DH problém.

\begin{poznamka}
Uvedený postup funguje aj pre ľubovoľné $x, u$. Stačí výslednú hodnotu
$g^{ba+bux}$ vydeliť hodnotou $(g^b)^{ux}$, potom dostaneme $g^{ba}$, čo sme chceli dostať.
\end{poznamka}

Čo by stalo ak by sme v protokole v 4. kroku neposielali $g^b + v$ ale len $g^b$?
Na prvý pohľad to vyzerá bezpečne, keďže uživateľ stále potrebuje poznať hodnotu $x$
(to čo by počítal by bolo $(g^b)^{a+ux}$). Problém je ale keď sa útočník bude vydávať
za server. Komunikácia prebehne štandartne až do 7. kroku (uživateľ posiela $H(A,S,K)$).
Následne útočník spustí slovníkový útok nasledovne:
Tipne si heslo $P'$, vypočíta $x' = H(s,P'), v' = g^x$ a následne aj:
$K' = H((g^a v'^u)^b)$. Teraz mu stačí porovnať $H(A,S,K')$ s tým čo dostal v 7. kroku.

Ďalšou vecou je prítomnosť náhodného $u$ v protokole. Pokiaľ túto hodnotu dokáže
útočník predvídať tak máme problém, pokiaľ sa mu už dostala do rúk hodnota $v$.
Útočník sa v tomto prípade vie maskovať ako užívateľ tým, že v 3. kroku pošle miesto
$g^a$ hodnotu $g^a v^{-u}$. Výsledná hodnota $K$ bude (opäť pre jednoduchosť vynecháva krok hašovania):
$K = (\alpha v^u)^b = (g^a v^{-u} v^u)^b = g^{ab}$. A túto hodnotú vie útočník
rátať bez znalosti hodnoty $x$ (stačí mu spočítať $((g^b + v) - v)^a$).
